class_name Heap

var array := []


func get(_property = null):
	if not array:
		return
	return array[0]


func pop():
	return remove_by_index(0)


func clear():
	array.clear()


func insert(value):
	array.append(value)
	up(array.size() - 1)


func remove(value):
	var index = array.find(value)
	if index >= 0:
		remove_by_index(index)


func remove_by_index(index):
	var length = array.size() - 1
	if index > length:
		return
	var r = array[index]
	if length > 0:
		array[index] = array[length]
		if down(index, length):
			up(index)
	array.pop_back()
	return r


func up(curr):
	var old = curr
	var arr = array
	var ele = arr[curr]

	var parent = floor((curr - 1) / 2)
	while parent >= 0:
		var e = arr[parent]
		if next_time_cmp(ele, e) >= 0:
			break
		arr[curr] = e
		curr = parent
		parent = floor((curr - 1) / 2)
	if old != curr:
		arr[curr] = ele
		return true
	return false


func down(curr, length):
	var old = curr
	var arr = array
	var ele = arr[curr]

	var left = curr * 2 + 1
	var right = left + 1
	while left < length:
		var child = left
		var e = arr[left]
		if right < length && next_time_cmp(arr[right], e) < 0:
			child = right
			e = arr[right]

		if next_time_cmp(ele, e) <= 0:
			break
		else:
			arr[curr] = e

			curr = child
			left = curr * 2 + 1
			right = left + 1
	if old != curr:
		arr[curr] = ele
		return true
	return false


func next_time_cmp(a, b) -> int:
	return a.next_time - b.next_time
